package 回溯;

import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 数组拆分为斐波那契数列842.java
 * @createTime 2023年02月13日 17:32:00
 */
public class 数组拆分为斐波那契数列842 {
	public static void main(String[] args) {
		splitIntoFibonacci("1101111");
	}
	public static List<Integer> splitIntoFibonacci(String num) {
		backTrace(num.toCharArray(), 0);
		return list;
	}

	static LinkedList<Integer> list = new LinkedList<>();

	public static boolean backTrace(char[] nums, int index) {
		if (nums.length == index && list.size() >= 3) {
			return true;
		}
		int temp = 0;
		for (int i = index; i < nums.length; i++) {
			//两位数以上不能0开头
			if (nums[index] == '0' && i > index) {
				break;
			}
			//截取
			temp = temp * 10 + nums[i] - '0';
			//数组小于3
			if (list.size() < 3) {
				list.add(temp);
				if (backTrace(nums, index + 1)) {
					return true;
				}
				list.removeLast();
			}
			else if (temp > list.getLast() + list.get(list.size() - 2)) {
				break;
			}
			else if (temp == list.getLast() + list.get(list.size() - 2)) {
				list.add(temp);
				if (backTrace(nums, index + 1)) {
					return true;
				}
				list.removeLast();
			}
		}
		return false;
	}
}
